package LC;

/**
 * https://leetcode.com/problems/jump-game-ii/description/
 * Given an array of non-negative integers,
 * you are initially positioned at the first index of the array.
 * Each element in the array represents your maximum jump length at that position.
 * Your goal is to reach the last index in the minimum number of jumps.
 * For example:
 * Given array A = [2,3,1,1,4]
 * The minimum number of jumps to reach the last index is 2.
 * (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
 */
public class LC_045_JumpGameII_Greedy {
    public static void main(String[] args) {
        int[] a = {2, 3, 1, 1, 4};
        int res = Solution.jump(a);
        System.out.println(res);
    }

    static class Solution {
        static int jump(int[] nums) {
            if (nums == null || nums.length == 0) return -1;
            int cur = 0;
            int last = 0;
            int step = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i > last) {
                    step++;
                    last = cur;
                }
                cur = Math.max(cur, nums[i] + i);
            }
            return cur < nums.length - 1 ? -1 : step;
        }
    }

}
